//
//  main.cpp
//  SA
//
//  Created by 李冰瑶 on 2017/11/4.
//  Copyright © 2017年 李冰瑶. All rights reserved.
//

#include<iostream>
#include<cstring>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<algorithm>
using namespace std;

#define MAXN 120
#define servers 4
#define T     3000    //初始温度
#define EPS   1e-8    //终止温度
#define DELTA 0.98    //温度衰减率
#define LIMIT 10000   //概率选择上限
#define OLOOP 100    //外循环次数
#define ILOOP 15   //内循环次数

string id[MAXN];  //字符串(10010100)
string s;
int idBinToTen[MAXN];
//int countOfServer[4] = {5,5,5,5};
int num = MAXN / servers;
int countOfServer[4] = {num,num,num,num};
int a[MAXN];
int cft_num[MAXN];  //记录每个id的冲突值
int cft_server[servers];  //记录每个server的冲突值
double Ex[servers];  //记录每个server均值
double Dx[servers];  //记录每个server方差


int x ;   //交换值
int y ;   //交换值
int position_x;
int position_y;
string previous_x;


string temp_str = "0";

//string id[1000] = {"1110","0111","0111","1000","0101","1011","1011","1110","0010","0000","1100","1101","1010","1011","1111","0110","1010","0111","0100","1110","0101","0111","0001","1000","1110","0110","1100","0001","1010","0001","0101","0011","0001","1001","0101","0011","1001","1011","1000","1110","1100","0010","0000","1111","1011","0000","0000","1100","1010","1011","1110","1010","1101","0110","0100","0000","0100","1001","0101","0011","0001","1101","0111","0111","0111","1100","0101","1001","1011","1100","0011","0001","1111","1000","0011","0001","0011","1001","1011","0111","1100","0000","0110","0100","1000","0010","1100","1111","1101","1100","0011","0100","1111","1001","1011","0101","1101","1000","1111","0001","0000","1111","0110","1000","0010","0000","0101","0100","0011","1011","1011","0001","0010","0111","1010","0110","1000","0111","1100","0011","1000","1111","1000","0010","1110","0101","0110","1001","0000","0010","1001","0000","1010","0001","1000","0000","0011","1110","0011","0111","0110","0110","0011","1101","1100","1101","0100","1011","1010","0000","1000","0010","0011","0100","1110","1100","0000","1101","0010","1011","1001","0100","0111","1111","0100","1111","0011","0100","1110","0010","0000","1001","0001","1000","0000","0010","0101","1011","0010","1001","1010","0010","0101","1100","0011","1000","1101","0100","1011","0010","1100","0101","0111","0001","0110","1011","0010","1010","0001","1000","0001","0000","1010","0000","0100","1101","0100","1010","1110","0001","0010","0001","0110","1101","1101","0100","1001","0000","1100","0101","0000","1001","0000","0011","1000","0010","1001","1111","1110","0011","0001","1110","1111","1110","1100","1111","0001","0100","0101","1111","0100","1011","0101","1100","0011","1100","0110","1000","0101","1000","111001","110111","100001","011011","101111","100010","000011","001101","101010","111111","011010","100111","010011","100101","011100","011000","111001","101100","000110","100001","010100","110001","100101","010011","100110","111000","111011","000010","000011","111011","000000","001100","101010","111110","101011","010110","010000","000100","100101","010011","000111","010111","011101","111100","010110","011011","110000","110001","111110","000011","000100","111001","101101","111100","000001","100100","100000","101100","111111","011100","001101","001111","100110","110101","110110","001111","000100","001111","011010","000010","000001","010100","001110","111011","000100","100111","101001","101000","011111","000011","100011","111000","001011","100101","011010","010000","001010","010000","101000","011000","000000","111110","001101","110110","011000","111101","110011","010100","101110","100000","100000","100011","010011","101100","000011","010010","101110","010100","011111","110100","111100","110100","111000","100000","100100","011000","000000","100101","101100","101001","101000","100101","110000","111000","110101","001011","001011","000101","011100","010110","101100","101010","000110","000001","000010","100000","010011","010100","101011","100001","001000","010110","110111","010100","100100","001100","010100","001001","000000","111000","001010","011111","111000","110001","111011","111110","110011","110001","010001","011111","010010","110101","110000","111100","011010","000101","100001","100001","110101","011001","001101","101010","000110","000110","001000","101010","000010","011010","111011","001101","011100","101011","001000","111001","011011","010001","110010","101000","000110","000101","011101","100111","011001","010111","111001","101101","001110","100100","100101","010110","101101","110111","101001","111110","101000","110111","010110","111111","110101","001010","100101","000010","111100","001000","100110","100011","010100","000011","111101","001111","111000","001001","110100","110110","111111","100100","011001","101010","011001","101001","100111","101001","110110","110011","100010","011011","011101","110100","011110","100100","111110","101000","110101","010101","001101","100011","011011","110100","111011","010001","11100111","01111000","01011011","10111110","00100000","11001101","10101011","11110110","10100111","01001110","01010111","00011000","11100110","11000001","10100001","01010011","00011001","01010011","10011011","10001110","11000010","00001111","10110000","00001100","10101011","11101010","11010110","01000000","01001001","01010011","00011101","01110111","01111100","01011001","10111100","00110001","11111000","00110001","00111001","10110111","11000000","01100100","10000010","11001111","11011100","00110100","11111001","10110101","11011000","11110001","00001111","01101000","00100000","01010100","00111011","10110001","00100111","10100110","10000111","11000011","10001111","10000010","11100101","01101001","00000010","10010000","10100001","10000000","00111110","00110111","01100110","00111101","11001101","01001011","10100000","10000010","00110100","11101100","00001101","00101011","10010100","01111111","01001111","00110100","11100010","00001001","00011000","00000010","01011011","00101001","10100010","01011100","00111000","11010100","10110010","11000101","01110001","01101011","00101010","00011000","00010000","10100000","01001101","01001010","11100001","00100001","01101101","11010100","10010000","11000101","00001001","00000011","10000010","10011111","11100011","00011110","11111110","11001111","00010100","01011111","01001011","01011100","00111100","01101000","01011000","01100001","11010101","10010011","01101010","00011000","01100010","00101010","00001001","10101110","11001101","01110010","10110010","00111001","01101101","00011100","10101000","00011000","01010111","01100111","01100101","01111110","01101101","00111010","01001001","01010110","10110111","01111010","01111110","10100011","01110101","10111111","11010100","10101001","01000010","11110000","10001001","10100011","01010000","00111111","01001111","11100000","10011101","00110110","11111110","01000110","01101010","01100110","10011001","11101001","11011011","00111000","10011011","01110111","01000111","10100100","11111010","10001101","01010101","00110110","00110110","11110100","11101101","00010100","00111010","11100000","11011000","00111000","11001010","11111010","01101110","11001011","00001011","10100010","11101011","01001100","00101011","01010111","11000110","01110101","11110010","01000000","10101100","10110011","01111010","00000111","00100101","01101001","10111111","11110010","01111011","10101011","01011001","01110001","10011111","00010010","00110100","10011011","01001111","10011100","10010111","00100110","11001011","01100110","10111000","00000001","00110110","00001011","01001001","10110001","11100101","00101110","01011110","01111101","10001110","00100101","10001100","11110111","01100001","01110010","00110001","10001000","00011001","11001001","00010111","00111001","1110011101","1110000101","1011101111","1000100000","1100110110","1010111111","0110101001","1101001110","0101011100","0110001110","0110110000","0110100001","0101001100","0110010101","0011100110","1110001110","1100001000","0011111011","0000000011","0010101011","1110101011","0101100100","0000010010","0101010011","0001110101","1101110111","1100010110","0110111100","0011000111","1110000011","0001001110","0110110111","1100000001","1001001000","0010110011","1111011100","0011010011","1110011011","0101110110","0011110001","0000111101","1010000010","0000010101","0000111011","1011000100","1001111010","0110100001","1111000011","1000111110","0000101110","0101011010","0100000010","1001000010","1000011000","0000001111","1000110111","0110011000","1111011100","1101010010","1110100000","1000001000","1101001110","1100000011","0100101011","1001010001","1111110100","1111001101","0011100010","0000100100","0110000000","0010010110","1100101001","1010001001","0111000011","1000110101","0010110010","1100010101","1100010110","1011001010","1000011000","0001000010","1000000100","1101010010","1011100001","0010000101","1011011101","0100100100","0011000101","0000100100","0000111000","0010100111","1111100011","0001111011","1111101100","1111000101","0001011111","0100101101","0111000011","1100011010","0001011000","0110000111","0101011001","0011011010","1000011000","0110001000","1010100000","1001101011","1011001101","0111001010","1100100011","1001011011","0100011100","1010100000","0110000101","0111011001","1101100101","0111111001","1011010011","1010010010","0101010110","1011011101","1110100111","1110101000","1101110101","1011111111","0101001010","1001010000","1011110000","1000100110","1000110101","0000001111","1101001111","1110000010","0111010011","0110111111","1001000110","0110101001","1001101001","1001111010","0111011011","0011100010","0110110111","0111010001","1110100100","1111101010","0011010101","0101001101","1000110110","1111010011","1011010001","0100001110","1011100000","1101100000","1110001100","1010111110","1001101110","1100101100","0010111010","0010111010","1101001100","0010101101","0101111100","0110011101","0111110010","0100000010","1011001011","0011011110","1000000111","0010010101","1010011011","1111111100","1001111011","1010101101","0110010111","0001100111","1100010010","0011010010","0110110100","1111100111","0010010111","0010011011","0010110110","0110101110","0000000001","0011011000","0010110100","1001101100","0111100101","0010111001","0111100111","1101100011","1000100101","1000110011","1101110110","0001011100","1000110001","1000100000","0110011100","1001000101","1100111001","0110111001","1101011001","1000010000","1010101101","1001111011","0010111100","0101110011","0011001001","1000011101","0101111100","0010101100","0100100011","1101001001","0010000000","0110011010","1011110111","0001011001","0111010011","0011010101","1001111101","0000000111","1011100100","0101011011","1000101100","1000111101","0001101100","1111011100","0001111011","1100000110","0011101011","1000110111","0001011001","0101001001","0110100001","0100011001","1110001000","1100011010","0010110100","0011100101","1110000110","0111101001","1101110011","1111000010","1001000110","0110011111","1110011111","1100101010","1101111001","1110011110","1101111110"};

//string id[64] = {"1110","0111","0111","1000","0101","1011","1011","1110","0010","0000","1100","1101","1010","1011","1111","0110","1010","0111","0100","1110","0101","0111","0001","1000","1110","0110","1100","0001","1010","0001","0101","0011","0001","1001","0101","0011","1001","1011","1000","1110","1100","0010","0000","1111","1011","0000","0000","1100","1010","1011","1110","1010","1101","0110","0100","0000","0100","1001","0101","0011","0001","1101","0111","0111"};
//产生MAXN个随机id
void div()
{
    srand((unsigned)time(NULL));
    for(int i = 0; i < MAXN; i++)
    {
        s = "";
        a[i] = rand() % MAXN;
        /*int j = i;
        while(j--)
        {
            if(a[i] == a[j])
            {
                a[i] = rand() % MAXN;
                j = i;
            }
        }*/
        if(a[i] == 0)
            id[i] = "00";
        else
        {
            for(int t = a[i]; t>0; t/=2)
                s = s + (t % 2 ? '1':'0');
            reverse(s.begin(), s.end()); 
            if(s.length() % 2 ==1)
                id[i] = temp_str + s; 
            else   
                id[i] = s;
        }     
    }    
}

void power(string s)
{
    unsigned int i=0;
    const char * pch = s.c_str();
    while(*pch == '0'|| *pch =='1')
    {
    	i<<=1;
    	i|= *pch++ -'0';
    }
    //cout<<i<<endl;
}

//输出每个服务器的字符串
void print_id()
{
    int t = 0;
	for(int i=0; i<servers; i++)
    {
        cout<<"server "<<i<<" ";
        for(int j = t; j < t+countOfServer[i]; j++)
            cout<<id[j]<<" ";
        cout<<endl;
        t += countOfServer[i];
    }
}


//比较字符串
int compare(string s1, string s2)
{
    int res, ans = 1;
    int l1, l2, len;
    l1 = (int)s1.length();
    l2 = (int)s2.length();

    if(l1 != l2)
    {
        if(l1 > l2)
            len = l2;
        else
            len = l1;

        for(int i=0; i<len; i++)
        {
            if(int(s1.c_str()[i]) != int(s2.c_str()[i]))
            {
                ans = 0;
                break;
            }
        }
        //res = s1.compare(0, len-1, s2, 0, len-1);
    }
    else
    {
        if(l1 == 2)
        {
            for(int i=0; i<2; i++)
            {
                if(int(s1.c_str()[i]) != int(s2.c_str()[i]))
                {
                    ans = 0;
                    break;
                }
            }    
        }
        else
        {
            for(int i=0; i<l1-2; i++)
            {
                if(int(s1.c_str()[i]) != int(s2.c_str()[i]))
                {
                    ans = 0;
                    break;
                }
            }
        }
        //res = s1.compare(0, l1-3, s2, 0, l2-3);
    }
    return ans;
} //输出0不等，不冲突；输出1相等，冲突



//计算每一个串的冲突值
void conflict()
{
    //div();
    memset(cft_num, 0, MAXN);
    int num_ans;
    int ser_ans;
    int count = 0;
    for(int i=0; i<servers; i++)
    {
        num_ans = 0;
        ser_ans = 0;

        for(int j = count; j < count+countOfServer[i]; j++)
        {
            int t = count + countOfServer[i];
            while((t--) > (j))
            {
                
                num_ans += compare(id[j],id[t]);
                //cout<<j<< " "<<t<<" "<<ans<<endl;
            }
            cft_num[j] = num_ans-1;
            num_ans = 0;
            ser_ans += cft_num[j];
        }
        cft_server[i] = ser_ans;
        count += countOfServer[i];
    }
    /*for(int i=0; i<MAXN; i++)
        cout<<cft_num[i]<<endl;
    for(int i=0; i<servers; i++)
        cout<<cft_server[i]<<endl;
    cout<<endl<<endl;*/
    //EX();
    //DX();
}

//每一个server均值
double EX()
{  
	double ans = 0;
    for(int i=0; i<servers; i++)
    {
        Ex[i] = (double)cft_server[i] / countOfServer[i];
        ans += Ex[i];
    }
    return ans;
}

void print_EX()
{
	for(int i=0; i<servers; i++)
        cout<<"server"<<i<<"的均值是："<<Ex[i]<<endl;
}


//每一个server方差
double DX()
{
    double ans;
    double sum = 0;
    int count = 0;
    for(int i=0; i<servers; i++)
    {
        ans = 0.0;
        for(int j = count; j < count+countOfServer[i]; j++)
            ans += pow((cft_num[j] - cft_server[i]),2);
        Dx[i] = ans / countOfServer[i]; 
        sum += Dx[i];
        count += countOfServer[i];
    }
    return sum;
}

void print_DX()
{
	for(int i=0; i<servers; i++)
        cout<<"server"<<i<<"的方差是："<<Dx[i]<<endl;
}





//随意交换两个字符串位置
void getNext()
{

	x = rand() % MAXN;
    y = rand() % MAXN;
    while(x == y)
    {
    	x = rand() % MAXN;
        y = rand() % MAXN;
    }
    
    //cout<<x<<" "<<y<<endl;
    int count = 0;

    //判断id[x]所在server
    for(int i=0; i<servers; i++)
    {
        if(x <= count + countOfServer[i])
        {
            countOfServer[i] --;
            position_x = i;
            break;
        }
        count += countOfServer[i];
        
    }
    //判断id[y]所在server
    count = 0;
    for(int i=0; i<servers; i++)
    {
        if(y <= count + countOfServer[i])
        {
            countOfServer[i] ++;
            position_y = i;
            break;
        }
        count += countOfServer[i];
    }
    

    previous_x = id[x];
    if(x > y)
    {
        for(int i=x; i>y; i--)
        {
            id[i] = id[i-1];
        }
        
        id[y] = previous_x;

    }
    else
    {
        for(int i=x; i<y; i++)
        {
            id[i] = id[i+1];
        }
        id[y] = previous_x;
    }
    
	//id[x].swap(id[y]);
	conflict();	
}


void SA()
{
	double t = T;
	srand(time(NULL));

	double cur_EX = EX();
	double new_EX;

	//double cur_DX = DX();
	//double new_DX;

	int P_L = 0;    // 连续找到更差结果的次数
    int P_F = 0;    // while循环次数
    while (1)       //外循环，主要更新参数t，模拟退火过程
    {
    	for (int i = 0; i < ILOOP; i++)    //内循环，寻找在一定温度下的最优值
        {
            getNext();
            new_EX = EX();
            //new_DX = DX();

            double dE = new_EX - cur_EX;
            //double dE = new_DX - cur_DX;

            if (dE < 0)   //如果找到更优值，直接更新
            {
                cur_EX = new_EX;
                //cur_DX = new_DX;

                P_L = 0;
                P_F = 0;
            }
            else
            {
                double rd = rand() / (RAND_MAX + 1.0);

                // dE取负数才有可能接受更差解,否则e>1
                double e = exp(-dE / t);
                if ( e > rd && e < 1)   //如果找到比当前更差的解，以一定概率接受该解，并且这个概率会越来越小
                    cur_EX = new_EX;
                	//cur_DX = new_DX;
                else
                {
                    if(x>y)
                    {
                        for(int i=y; i<x; i++)
                        {
                            id[i] = id[i+1];
                        }
                        id[x] = previous_x;
                    }
                    else
                    {
                        for(int i=y; i>x; i--)
                        {
                            id[i] = id[i-1];
                        }
                        id[x] = previous_x;
                    }
                    countOfServer[position_x]++;
                    countOfServer[position_y]--;
                	
                }

                P_L++;
            }
            if (P_L > LIMIT)
            {
                P_F++;
                break;
            }
        }
        if (P_F > OLOOP || t < EPS)
            break;
        t *= DELTA;
    }
}


/*int main()
{
	clock_t startTime, endTime;
	startTime = clock();
    //div();
    print_id();
    conflict();
    //cout<<EX()<<endl;
    cout<<DX()<<endl;
    //print_EX();
    print_DX();
    cout<<"computing..."<<endl;
    
    SA();
    print_id();
    //cout<<EX()<<endl;
    cout<<DX()<<endl;
    //print_EX();
    print_DX();
    cout<<"finished..."<<endl;
    endTime = clock();
    cout<<"运行时间："<<(double)(endTime - startTime) / CLOCKS_PER_SEC<<"s"<<endl;

}*/
int main()
{
    //print_id();
    clock_t startTime, endTime;
    startTime = clock();
    div();
    for(int i=0; i<MAXN; i++)
        cout<<id[i]<<" ";
    cout<<endl;
    conflict();
    EX();
    print_EX();
    cout<<"computing..."<<endl;
    SA();
    for(int i=0;i<MAXN;i++)
	idBinToTen[i]=power(id[i]);
    for(int i=0; i<countOfServer[0]; i++)
        cout<<id[i]<<" ";
    cout<<"server0"<<endl<<endl;
    cout<<endl;

    for(int i=countOfServer[0]; i<countOfServer[0]+countOfServer[1]; i++)
        cout<<id[i]<<" ";
    cout<<"server1"<<endl<<endl;
    cout<<endl;

    for(int i=countOfServer[0]+countOfServer[1]; i<countOfServer[0]+countOfServer[1]+countOfServer[2]; i++)
        cout<<id[i]<<" ";
    cout<<"server2"<<endl<<endl;
    cout<<endl;

    for(int i=countOfServer[0]+countOfServer[1]+countOfServer[2]; i<countOfServer[0]+countOfServer[1]+countOfServer[2]+countOfServer[3]; i++)
        cout<<id[i]<<" ";
    cout<<"server3"<<endl<<endl;
    cout<<endl;

    EX();
    print_EX();
    endTime = clock();
    cout<<"运行时间："<<(double)(endTime - startTime) / CLOCKS_PER_SEC<<"s"<<endl;
    string s="1001";
    power(s);

}
